package demo9;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Solution {

    //1.对称二叉树(dfs)
    public boolean isSymmetricChild(TreeNode leftRoot, TreeNode rightRoot) {
        if(leftRoot == null && rightRoot == null) {
            return true;
        }
        if((leftRoot == null && rightRoot != null) ||
                (leftRoot != null && rightRoot == null)) {
            return false;
        }
        if(leftRoot.val != rightRoot.val) {
            return false;
        }
        //再去对比左树的左树与右树的右树...
        return isSymmetricChild(leftRoot.left, rightRoot.right) &&
                isSymmetricChild(leftRoot.right, rightRoot.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        //将左右子树分开来看
        return isSymmetricChild(root.left, root.right);
    }

//    //2.二叉树的最大深度(dfs)
//    private int max;
//    public int maxDepth(TreeNode root) {
//        dfs(root, 1);
//        return max;
//    }
//
//    public void dfs(TreeNode root, int cur) {
//        if(root == null) {
//            return;
//        }
//        if(cur > max) {
//            max = cur;
//        }
//        dfs(root.left, cur + 1);
//        dfs(root.right, cur + 1);
//    }

    //二叉树的最大深度(dfs2)
//    public int maxDepth(TreeNode root) {
//        return depth(root, 0);
//    }
//
//    public int depth(TreeNode root, int cur) {
//        if(root == null) {
//            return cur;
//        }
//        return Math.max(depth(root.left, cur + 1),
//                depth(root.right, cur + 1));
//    }

    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        //左右子树的最大值再加上自己本身
        return Math.max(left, right) + 1;
    }

//    //4.二叉树的最小深度(dfs)
//    private int min = Integer.MAX_VALUE;
//    public int minDepth(TreeNode root) {
//        if(root == null) return 0;
//        dfs(root, 1);
//        return min;
//    }
//
//    public void dfs(TreeNode root, int cur) {
//        if(root == null) return;
//        dfs(root.left, cur + 1);
//        dfs(root.right, cur + 1);
//        if(root.left == null && root.right == null) {
//            if(cur < min) {
//                min = cur;
//            } else {
//                return;
//            }
//        }
//    }

    //5.二叉树的最小深度(dfs2)
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if(root.left == null && root.right != null) {
            return 1 + right;
        }
        if(root.left != null && root.right == null) {
            return 1 + left;
        }
        return Math.min(left, right) + 1;
    }

    //6.完全二叉树的节点个数(dfs)
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null) {
            return 1;
        }
        int left = countNodes(root.left);
        int right = countNodes(root.right);
        return left + right + 1;
    }

//    //7.平衡二叉树(dfs)
//    public boolean isBalanced(TreeNode root) {
//        //就是对每一颗树的左右子树求最大深度(因为是叶子结点)，深度差必须小于等于1
//        if(root == null) {
//            return true;
//        }
//        boolean left = isBalanced(root.left);
//        boolean right = isBalanced(root.right);
//        return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 &&
//                left && right;
//    }
//
//    //求最大深度深度
//    public int getDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        int left = getDepth(root.left);
//        int right = getDepth(root.right);
//        return Math.max(left, right) + 1;
//    }

    //7.平衡二叉树(dfs优化)
    public boolean isBalanced(TreeNode root) {
        //就是对每一颗树的左右子树求最大深度(因为是叶子结点)，深度差必须小于等于1
        if(root == null) {
            return true;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        return Math.abs(left - right) <= 1 &&
                isBalanced(root.left) &&
                isBalanced(root.right);
    }

    //求最大深度深度
    public int getDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        return Math.max(left, right) + 1;
    }


    //8.二叉树的所有路径(dfs + 回溯)
    private List<String> list = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        StringBuilder path = new StringBuilder();
        dfs(root, path);
        return list;
    }


    public void dfs(TreeNode root, StringBuilder path) {
        if(root == null) {
            return;
        }
        path.append(root.val);
        //记录元素长度，方便剪枝
        int size = String.valueOf(root.val).length();
        //走完一个路径
        if(root.left == null && root.right == null) {
            list.add(new String(path));
            path.delete(path.length() - size, path.length());
            return;
        }
        path.append("->");
        dfs(root.left, path);
        dfs(root.right, path);
        //清除
        path.delete(path.length() - size - 2, path.length());
    }

//    //9.左叶子结点之和
//    private int sum;
//    public int sumOfLeftLeaves(TreeNode root) {
//        dfs(root, null);
//        return sum;
//    }
//
//    public void dfs(TreeNode root, TreeNode parent) {
//        if(root == null) {
//            return;
//        }
//        //找到叶子结点
//        if(root.left == null && root.right == null && parent != null &&
//                parent.left == root) {
//            sum += root.val;
//            return;
//        }
//        parent = root;
//        dfs(root.left, parent);
//        dfs(root.right, parent);
//    }

    //10.路径之和(dfs)
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        targetSum -= root.val;
        //叶子结点
        if(root.left == null && root.right == null) {
            if(targetSum == 0) {
                return true;
            } else {
                return false;
            }
        }
        return hasPathSum(root.left, targetSum) ||  hasPathSum(root.right, targetSum);
    }

}

class Main {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);

        treeNode1.left = treeNode2;
        treeNode2.right = treeNode5;
        treeNode1.right = treeNode3;

        Solution solution = new Solution();
        solution.binaryTreePaths(treeNode1);
    }

}

